This invention relates generally to stroke-based rendering, and in particular to verifying the occlusion of strokes in a still image or in a frame of a stroke-based animation.
Non-photorealistic rendering (NPR) is a subfield of computer graphics that offers additional variety in the looks afforded by computer generated animations. In this field, much time and effort have been spent researching algorithms to produce renderings that could imitate traditional media in a variety of artistic styles. Within non-photorealistic rendering, stroke-based rendering is a popular technique in which an image is created by the sequential drawing of atomic image-space discrete elements (the strokes). Painterly Rendering, for instance, is a well known example of stroke-based rendering where each stroke simulates a brush stroke and is rendered through, e.g., an oil painting media simulation. For example, impressionist paintings can be successfully imitated using this technique.
The input to stroke-based rendering can either be two-dimensional (e.g., an image or video) or three-dimensional (e.g., a three-dimensional model for an animated scene). In three-dimensional stroke-based rendering, the three-dimensional surfaces of the scene are rendered using image-space surface elements, or strokes. Each stroke is associated with a three-dimensional point on an object of the scene, which is the stroke's three-dimensional anchor point. The stroke thus depicts a portion of surface for the object to which the stroke belongs around that anchor point.
As opposed to photorealistic rendering, the drawing marks used for depiction in NPR stroke-based rendering (e.g., brush strokes) are typically individually distinguishable in the final result. Due to their extent in a particular image, or frame in an animation, the strokes can overlap. As a consequence, the order in which overlapping frames are drawn visually influences the resulting frame. For instance, if Vp and Vq are two overlapping strokes, drawing Vp and then Vq would produce a different image than drawing Vq and then Vp.
The order in which some of the strokes should be drawn naturally arises from geometric constraints present in the scene, such as when two overlapping strokes Vp and Vq depict an occlusion in the scene. For example, when the patch of surface drawn by Vp either partially or completely occludes the patch of surface drawn by Vq, then Vq must be drawn before Vp to reflect the occlusion properly in the resulting frame. It can be noted that in typical scenes, the constraints imposed by occlusion of surfaces only partially constrain the ordering of the strokes in a given frame.
Enforcing a particular ordering only where it is necessary provides a useful flexibility for the renderer. Indeed, wherever the order between two strokes is not predetermined by occlusion or some other user-defined constraints, some stroke orderings might provide more aesthetic results than other orderings. It is therefore desirable to be able to identify whether two overlapping strokes define an occlusion when rendering a still image or a frame in stroke-based animation.
Three-dimensional stroke-based rendering was first introduced by Barbara Meier in 1994 and is described in her paper, Barbara J. Meier, Painterly Rendering for Animation, Proc. of Computer Graphics, 1996, p. 477-484. In this system, three-dimensional particles are placed onto the objects of the scene, and each particle is associated with a stroke in two-dimensional image space whose visual attributes are queried from reference images at the point. To render occlusions properly, strokes are sorted according to the depth of their corresponding particles before being drawn in image space. Although such an ordering allows for a proper depiction of visibility, enforcing depth ordering for all strokes is not flexible enough for production quality stroke-based rendering.
Since Meier's paper, no further work has been done in stroke-based rendering to overcome these limitations. The field of point-based rendering, which became popular in the last few years, also uses image-space surface elements to render three-dimensional geometry using a technique known as splatting, which can be categorized as stroke-based rendering. As opposed to NPR stroke-based rendering, e.g. painterly rendering, however, splatting attempts to simulate continuous surface shading and uses filtering to prevent individual strokes to be distinguishable. As a result, simple visibility algorithms, such as depth ordering, are sufficient to produce the desired result. But these techniques used for splatting would generally not be flexible enough in stroke-based rendering where the strokes are individually visible.
Techniques are thus desired for characterizing occlusion by identifying whether overlapping strokes define an occlusion in the context of three-dimensional stroke-based rendering.